其他
稳定匹配问题——稳定婚姻算法设计
点击上方“程序人生”，选择“置顶公众号”
第一时间关注程序猿（媛）身边的故事
图片源自：美剧《How I met your mother》
****
本代码带有详细的注释，并在控制台输出时详细地说明了算法的过程，非常有助于新手理解稳定匹配问题和稳定婚姻算法的设计思路。
****
using namespace std;
bool finish_or_not(int, int *);
bool current_male_is_better(int num, int *male_rank_in_female, int current, int chasing);
int main(){
int num = 5;
/*cout << "输入数目n：";
cin >> num;
cout << "数目：" << num << endl;
//男人和女人心目中异性的排行
int **female_rank_in_male, **male_rank_in_female;
female_rank_in_male = new int*[num];
male_rank_in_female = new int*[num];
for (int i = 0; i < num; i++){
female_rank_in_male[i] = new int[num];
male_rank_in_female[i] = new int[num];
}
for (int i = 0; i < num; i++){
for (int j = 0; j < num; j++){
cout << endl << "请输入男人" << i + 1 << "心目中的第" << j + 1 << "名：";
cin >> female_rank_in_male[i][j];
}
}
for (int i = 0; i < num; i++){
for (int j = 0; j < num; j++){
cout << endl << "请输入女人" << i + 1 << "心目中的第" << j + 1 << "名：";
cin >> male_rank_in_female[i][j];
}
}*/
int female_rank_in_male[5][5] = { { 2, 1, 4, 5, 3 }, { 4, 2, 1, 3, 5 }, { 2, 5, 3, 4, 1 }, { 1, 4, 3, 2, 5 }, { 2, 4, 1, 5, 3 } };
int male_rank_in_female[5][5] = { { 5, 1, 2, 4, 3 }, { 3, 2, 4, 1, 5 }, { 2, 3, 4, 5, 1 }, { 1, 5, 4, 3, 2 }, { 4, 2, 5, 3, 1 } };
//男人和女人正在约会的对象
int *date_of_male = new int[num];
int *date_of_female = new int[num];
for (int i = 0; i < num; i++){
date_of_male[i] = 0;
date_of_female[i] = 0;
}
//男人追求过的女人的数量
int *num_of_chased_female = new int[num];
for (int i = 0; i < num; i++){
num_of_chased_female[i] = 0;
}
while (finish_or_not(num, date_of_male) == false){//如果有男人没有约会对象
for (int i = 0; i < num; i++){//按序号遍历所有男人
cout << "正在查看男人 " << i + 1 << " 有没有约会对象..." ;
if (date_of_male[i] == 0){//如果某男人没有约会对象
cout << endl;
cout << "男人 " << i + 1 << " 没有约会对象！" << endl;
//该男人准备追的女人（该男人优先表中还没追求过的排名最高的女人）
int female_to_chase = female_rank_in_male[i][num_of_chased_female[i]];
//该男人准备追的女人的现任
int date_of_female_to_chase = date_of_female[female_to_chase - 1];
cout << "男人 " << i + 1 << " 准备追女人 " << female_to_chase << "，女人现任是 " << date_of_female_to_chase << endl;
if (date_of_female_to_chase == 0){//如果该男人准备追的女人没有现任
date_of_male[i] = female_to_chase;//该男人的约会对象变成准备追的女人
date_of_female[female_to_chase - 1] = i + 1;//男人准备追的女人的约会对象变成该男人
cout << "男人 " << i + 1 << " 和女人 " << female_to_chase << " 在一起了！" << endl;
}
else if (current_male_is_better(num, male_rank_in_female[female_to_chase - 1], date_of_female_to_chase, i + 1)){
//如果该男人准备追的女人的现任在女人心目中比该男人更好，则什么也不做
cout << "男人 " << i + 1 << " 被女人 " << female_to_chase << " 拒绝了！" << endl;
}
else{//如果该男人比该男人准备追的女人的现任在女人心目中更好
date_of_male[date_of_female_to_chase - 1] = 0;//该男人准备追的女人的现任回到单身状态
date_of_male[i] = female_to_chase;//该男人的约会对象变成准备追的女人
date_of_female[female_to_chase - 1] = i + 1;//该男人准备追的女人的约会对象变成该男人
cout << "男人 " << i + 1 << " 和女人 " << female_to_chase << " 在一起了！男人 " << date_of_female_to_chase << " 变成单身！" << endl;
}
num_of_chased_female[i]++;//该男人追过的女人数量加1
cout << "男人 " << i + 1 << " 追过的女人数目是 " << num_of_chased_female[i] << endl;
}
else{
cout << "查得已有对象：女人 " << date_of_male[i] << endl;
}
}
}
//最后的输出
cout << endl <<"男人：";
for (int i = 0; i < num; i++){
cout << i + 1 << " ";
}
cout << endl << "女人：";
for (int i = 0; i < num; i++){
cout << date_of_male[i] << " ";
}
cout << endl << endl;
/*
//删除数组
for (int i = 0; i < num; i++){
delete[] female_rank_in_male[i];
delete[] male_rank_in_female[i];
}
delete[] female_rank_in_male;
delete[] male_rank_in_female;*/
delete[] date_of_male;
delete[] date_of_female;
delete[] num_of_chased_female;
return 0;
}
bool finish_or_not(int num, int *date_of_male){
cout << endl << "排序：";
for (int i = 0; i < num; i++){
cout << date_of_male[i] << " ";
}
cout << endl << endl;
for (int i = 0; i < num; i++){
if (date_of_male[i] == 0){
cout << "还未完全匹配......" << endl << endl;
return false;
}
}
cout << "已完全匹配！！！" << endl;
return true;
}
//比较某女人现在的约会对象和追求者哪个在她心目中排行更高
//注意数组参数是一维（一位女人的优先表而不是所有女人的优先表）
bool current_male_is_better(int num, int *male_rank_in_female, int current, int chasing){
int rank_of_current, rank_of_chasing;
for (int i = 0; i < num; i++){
if (male_rank_in_female[i] == current){
rank_of_current = i;
}
if (male_rank_in_female[i] == chasing){
rank_of_chasing = i;
}
}
cout << "现任排名是 " << rank_of_current << " 追求者排名是 " << rank_of_chasing << endl;
if (rank_of_current < rank_of_chasing)
return true;
else
return false;
}更新：新增萌萌哒版本，像写小说一样说出来~
****
using namespace std;
bool finish_or_not(int, int *);
bool current_male_is_better(int num, int *male_rank_in_female, int current, int chasing);
int main(){
int num = 5;
int female_rank_in_male[5][5] = { { 2, 1, 4, 5, 3 }, { 4, 2, 1, 3, 5 }, { 2, 5, 3, 4, 1 }, { 1, 4, 3, 2, 5 }, { 2, 4, 1, 5, 3 } };
int male_rank_in_female[5][5] = { { 5, 1, 2, 4, 3 }, { 3, 2, 4, 1, 5 }, { 2, 3, 4, 5, 1 }, { 1, 5, 4, 3, 2 }, { 4, 2, 5, 3, 1 } };
for (int i = 0; i < num; i++){
cout << "男生 " << i << " 心目中妹子的排行：";
for (int j = 0; j < num; j++){
cout << female_rank_in_male[i][j] << " ";
}
cout << endl;
}
cout << endl;
for (int i = 0; i < num; i++){
cout << "女生 " << i << " 心目中男生的排行：";
for (int j = 0; j < num; j++){
cout << male_rank_in_female[i][j] << " ";
}
cout << endl;
}
//男生和妹子正在约会的对象
int *date_of_male = new int[num];
int *date_of_female = new int[num];
for (int i = 0; i < num; i++){
date_of_male[i] = 0;
date_of_female[i] = 0;
}
//男生追求过的妹子的数量
int *num_of_chased_female = new int[num];
for (int i = 0; i < num; i++){
num_of_chased_female[i] = 0;
}
do{//如果有男生没有对象
for (int i = 0; i < num; i++){//按序号遍历所有男生
cout << endl << "正在查看男生 " << i + 1 << " 有没有对象..." << endl;
if (date_of_male[i] == 0){//如果某男生没有对象
cout << "男生 " << i + 1 << " 没有对象！" << endl;
//该男生准备追的妹子（该男生优先表中还没追求过的排名最高的妹子）
int female_to_chase = female_rank_in_male[i][num_of_chased_female[i]];
//该男生准备追的妹子的现任
int date_of_female_to_chase = date_of_female[female_to_chase - 1];
cout << "男生 " << i + 1 << " 准备追妹子 " << female_to_chase;
if (date_of_female_to_chase != 0){
cout << "，妹子现任是 " << date_of_female_to_chase << endl;
}
else{
cout << "，妹子目前是单身的呢~" << endl;
}
if (date_of_female_to_chase == 0){//如果该男生准备追的妹子没有现任
date_of_male[i] = female_to_chase;//该男生的对象变成准备追的妹子
date_of_female[female_to_chase - 1] = i + 1;//男生准备追的妹子的对象变成该男生
cout << "这样子的话，男生 " << i + 1 << " 和妹子 " << female_to_chase << " 在一起了！" << endl;
}
else if (current_male_is_better(num, male_rank_in_female[female_to_chase - 1], date_of_female_to_chase, i + 1)){
//如果该男生准备追的妹子的现任在妹子心目中比该男生更好，则什么也不做
cout << "所以！男生 " << i + 1 << " 被妹子 " << female_to_chase << " 拒绝了！" << endl;
}
else{//如果该男生比该男生准备追的妹子的现任在妹子心目中更好
date_of_male[date_of_female_to_chase - 1] = 0;//该男生准备追的妹子的现任回到单身状态
date_of_male[i] = female_to_chase;//该男生的对象变成准备追的妹子
date_of_female[female_to_chase - 1] = i + 1;//该男生准备追的妹子的对象变成该男生
cout << "所以！男生 " << i + 1 << " 和妹子 " << female_to_chase << " 在一起了！" << endl;
cout<< "与此同时，不幸的是，男生 " << date_of_female_to_chase << " 变成单身狗了QAQ" << endl;
}
num_of_chased_female[i]++;//该男生追过的妹子数量加1
}
else{
cout << "男生已经跟妹子 " << date_of_male[i] << " 在一起了呢~~下一个吧~~~" << endl;
}
}
} while (finish_or_not(num, date_of_male) == false);
//最后的输出
cout << endl << "┌───故事的结局───┐"<<endl;
cout << "│ │" << endl;
for (int i = 0; i < num; i++){
cout << "│ 男生" << i + 1 << " - "<< "女生" << date_of_male[i] <<" │"<< endl;;
}
cout << "│ │" << endl;
cout << "└───────────┘" << endl << endl;
delete[] date_of_male;
delete[] date_of_female;
delete[] num_of_chased_female;
system("pause");
return 0;
}
bool finish_or_not(int num, int *date_of_male){
for (int i = 0; i < num; i++){
if (date_of_male[i] == 0){
cout << "还有单身狗......再来~" << endl;
return false;
}
}
cout << endl << "已全部脱离单身狗行列！！！" << endl;
return true;
}
//比较某妹子现在的对象和追求者哪个在她心目中排行更高
//注意数组参数是一维（一位妹子的优先表而不是所有妹子的优先表）
bool current_male_is_better(int num, int *male_rank_in_female, int current, int chasing){
int rank_of_current, rank_of_chasing;
for (int i = 0; i < num; i++){
if (male_rank_in_female[i] == current){
rank_of_current = i;
}
if (male_rank_in_female[i] == chasing){
rank_of_chasing = i;
}
}
cout << "在妹子心目中现任排名是 " << rank_of_current << " ，而追求者排名则是 " << rank_of_chasing << endl;
if (rank_of_current < rank_of_chasing)
return true;
else
return false;
}喜欢这个「爱情故事」么？
- THE END -
本文作者：CSDN博客作者-theusProme
如果你有好的原创文章想与大家分享，欢迎投稿。
征稿要求：
①稿件字数以800~1500字左右为宜，多于2000字的文章在手机上阅读起来比较麻烦，少于800字的文章看起来不过瘾；
②你有自己拍的适合做文章插图的照片也可一并附上~如果不方便，程序和小七也会帮你配图~
加程序人生编辑们的微信，备注#投稿#：
程序 微信ID：druidlost
小七 微信ID：duoshangshuang
点击图片get往期内容